package sort;

/**
 * @author RunningShrimp
 * @date 2021/6/16  14:07
 * @see <a href=""></a>
 */
public class CountingSort extends BaseSort<Integer> {

    @Override
    public void sort(Integer[] array) {
        int max = getMaxValue(array);

        countingSort(array, max);
    }

    private void countingSort(Integer[] array, int max) {
        int bucketLen = max + 1;

        int[] bucket = new int[bucketLen];

        for (Integer value : array) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int i = 0; i < bucketLen; i++) {
            while (bucket[i] > 0) {
                array[sortedIndex++] = i;
                bucket[i]--;
            }
        }
    }

    private Integer getMaxValue(Integer[] array) {
        Integer max = array[0];
        for (Integer e : array) {
            if (less(max, e)) {
                max = e;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(5, 100);
        BaseSort<Integer> sort = new CountingSort();

        System.out.println("排序前：");
        sort.show(array);
        sort.sort(array);
        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
    }
}
